package com.practice.zuocy.base.class09;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 【题目】：
 * 输入：Capital、正数数组Profits、正数K、正数W
 * Capital[i]表示i号项目的花费
 * Profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
 * K表示你只能串行的最多做K个项目
 * W表示你的初始资金
 * 【说明】：每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 【输出】：你最后获得的最大钱数。
 */
public class Code05_IPO {

    /**
     * 贪心解法（使用堆）
     *
     * @param K       K表示你只能串行的最多做K个项目
     * @param W       W表示你的初始资金
     * @param Profits Profits[i]表示i号项目在扣除花费之后还能挣到的钱（利润）
     * @param Capital Capital[i]表示i号项目的花费
     * @return
     */
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital) {
        // 按花费排序的小根堆，表示此时被锁住的项目
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());
        // 按利润组织的大根堆，表示此时解锁的项目
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());
        // 初始被锁住的项目
        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }
        // 周而复始的解锁项目，做项目。最多做K个项目
        for (int i = 0; i < K; i++) {
            // 使用初始资金W在小根堆中去解锁项目，放到大根堆里面去
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W) {
                maxProfitQ.add(minCostQ.poll());
            }
            if (maxProfitQ.isEmpty()) {// 没有解锁任何项目
                return W;
            }
            W += maxProfitQ.poll().p;
        }
        return W;
    }

    public static class Program {
        public int p;
        public int c;

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c;
        }

    }

    public static class MaxProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;
        }

    }

}
